package algorithms.leaning.class22;

import common.util.MyUtil;

/**
 * 给定3个参数，N，M，K
 * 怪兽有N滴血，等着英雄来砍自己
 * 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * 求K次打击之后，英雄把怪兽砍死的概率
 *
 * @author guichang
 * @date 2021/6/23
 */

@SuppressWarnings("all")
public class Code1_动态规划_英雄砍死的概率 {

    public static void main(String[] args) {
        int N = 10, M = 5, K = 5;
        MyUtil.print(beingHacked(N, M, K));
        MyUtil.print(beingHackedDp(N, M, K));
    }

    public static double beingHacked(int N, int M, int K) {
        if (N <= 0 || M <= 0 || K <= 0) {
            return -1;
        }
        return 1 - (process(N, K, M) / Math.pow(M + 1, K));
    }

    /**
     * 还剩n滴血的情况下砍k刀还活着的概率
     */
    private static int process(int n, int k, int M) {
        // 砍完了
        if (k == 0) {
            return n > 0 ? 1 : 0;
        }
        int p = 0;
        for (int hp = 0; hp <= M; hp++) {
            // 没血了就不砍了
            if (n - hp > 0) {
                p += process(n - hp, k - 1, M);
            }
        }
        return p;
    }

    public static double beingHackedDp(int N, int M, int K) {
        if (N <= 0 || M <= 0 || K <= 0) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1; i <= N; i++) {
            dp[i][0] = 1;
        }
        // 整体从上到下，内部从左到右
        for (int n = 1; n <= N; n++) {
            for (int k = 1; k <= K; k++) {
                for (int hp = 0; hp <= M; hp++) {
                    // 没血了就不砍了 TODO 斜率优化
                    if (n - hp > 0) {
                        dp[n][k] += dp[n - hp][k - 1];
                    }
                }
            }
        }
        return 1 - (dp[N][K] / Math.pow(M + 1, K));
    }
}